import java.text.ParseException;

public class Queue<E> {

	private Node<E> header;
	private Node<E> tail;

	public Queue() {
		header = new Node<E>();
		tail = new Node<E>();

		header.next = tail;
		tail.previous = header;
	}

	public Queue(Node<E> node) {
		header = new Node<E>();
		tail = new Node<E>();

		header.next = node;
		node.previous = header;
		tail.previous = node;
		node.next = tail;
	}

	public Node<E> getNext() {
		if (!isEmpty()) {
			Node<E> removed = header.next;
			header.next = removed.next;
			removed.next.previous = header;
			return removed;
		}
		return null;
	}

	public void addNode(Node<E> node) {
		Node<E> auxiliar = tail.previous;
		tail.previous = node;
		node.next = tail;
		node.previous = auxiliar;
		auxiliar.next = node;
	}

	public Node<E> top() {
		if (!isEmpty()) {
			return header.next;
		}
		return null;
	}

	public Node<E> getNode(E value) {
		if (!isEmpty()) {
			boolean find = false;
			Node<E> nodeFind = null;
			do {
				nodeFind = top();
				if (nodeFind.value.equals(value)) {
					find = true;
				} else {
					getNext();
				}
			} while (!isEmpty() && !find);

			if (find) {
				return nodeFind;
			}
		}
		return null;
	}

	public Node<E> getNodeBiggerThan(E value) throws ParseException {
		if (!isEmpty()) {
			boolean find = false;
			Node<E> nodeFind = null;
			do {
				nodeFind = top();
				int nodeFindIntegerValue = Integer.parseInt(String.valueOf(nodeFind.value));
				int valueIntegerValue = Integer.parseInt(String.valueOf(value));
				if (nodeFind.value.equals(value) || nodeFindIntegerValue > valueIntegerValue) {
					find = true;
				} else {
					getNext();
				}
			} while (!isEmpty() && !find);

			if (find) {
				return nodeFind;
			}
		}
		return null;
	}

	public boolean isEmpty() {
		return (header.next.equals(tail));
	}

	public Queue<E> clone() {
		if (!isEmpty()) {
			Queue<E> clone = new Queue<E>();
			Queue<E> backUp = new Queue<E>();
			Node<E> node = null;

			do {
				node = getNext();
				clone.addNode(new Node<E>(node.value));
				backUp.addNode(new Node<E>(node.value));
			} while (!isEmpty());

			do {
				node = backUp.getNext();
				addNode(new Node<E>(node.value));
			} while (!backUp.isEmpty());

			return clone;
		}
		return null;
	}
}
